GATE CSE 2006
Q21.
In a binary max heap containing n numbers, the smallest element can be found in timeQ22.
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3-ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?Q23.
We consider addition of two 2's complement numbers b_{n-1}b_{n-2}...b_{0} and a_{n-1}a_{n-2}...a_{0}. A binary Combinational Circuit for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by c_{n-1}c_{n-2}...c_{0} and the carryout by c_{out} . Which one of the following options correctly identifies the overflow condition?Q24.
Consider the following C code segment. for (i = 0, < i n; i++) { for (j=0; j< n; j++) { if (i%2) { x += (4*j + 5*i); y += (7 + 4*j); } } } Which one to the following false?Q25.
Consider the following C-function in which a[n] and b[m] are two sorted integer arrays and c[n+m] be another integer array. void xyz (int a[],int b[],int c[]){ int i, j, k; i=j=k=0; while((i < n))&&(j < m) if (a[i] < b[j]c[k++]=a[i++]; else c[k++]=b[j++]; } Which of the following condition(s) hold(s) after the termination of the while loop ? I. j\ltm, k=n+j-1, and a [n-1]\ltb[j] if i=n II. i\ltn, k=m+i-1, and b[m-1]\leqa[i] if j=mQ26.
Consider a weighted complete graph G on the vertex set {v_{1},v_{2},...,v_{n}} such that the weight of the edge (v_{i},v_{j}) is 2|i-j|. The weight of a minimum spanning treeQ27.
Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal's algorithm?Q28.
A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?Q29.
Consider these two functions and two statements S1 and S2 about them. S1 : The transformation from work 1 to work 2 is valid, i.e., for any program state and input arguments, work 2 will compute the same output and have the same effect on program state as work 1 S2 : All the transformations applied to work 1 to get work 2 will always improve the performance (i.e. reduce CPU time) of work 2 compared to work 1Q30.
Consider a new instruction named branch-on-bit-set (mnemonic bbs). The instruction "bbs reg, pos, labbel" jumps to label if bit in position pos of register operand reg is one. a register is 32 bits wide and the bits are numbered 0 to 31, bit in position 0 being the least significant. Consider the following emulation of this instruction on a processor that does not have bbs implemented. temp\rightarrowreg & mask Branch to label if temp is non-zero The variable temp is a temporary register. For correct emulation the variable mask must be generated by